import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;

public class SentenceDecomposition
{
	public final static int mmax = 1000000000;
	public Integer dp[];
	public String str;
	public String[] list;

	public int decompose(String sentence, String[] validWords)
	{
		str = sentence;
		list = validWords;
		dp = new Integer[str.length() + 1];
		int ret = solve(str.length());
		return ret==mmax? -1 : ret;
	}

	public int solve(int len){
		if(dp[len] != null) return dp[len];
		dp[len] = mmax;
		if(len == 0){
			return dp[len] = 0;
		}
		for(String s: list){
			int len2 = s.length();
			if(len2 > len) continue;
			int cost = match(s, str.substring(len-len2, len));
			if(cost == -1) continue;
			dp[len] = Math.min(dp[len], cost + solve(len-len2));
		}
		return dp[len];
	}

	public int match(String a, String b){
		String c = sorted(a);
		String d = sorted(b);
		if(c.compareTo(d) != 0) return -1;
		int ret = 0;
		for(int i=0; i<a.length(); i++){
			if(a.charAt(i) != b.charAt(i))
				ret++;
		}
		return ret;
	}

	public String sorted(String a){
		char[] content = a.toCharArray();
		Arrays.sort(content);
		String ret = new String(content);
		return ret;
	}
	
	public static void main(String[] args)
	{
		long time;
		int answer;
		boolean errors = false;
		int desiredAnswer;
		
		
		time = System.currentTimeMillis();
		answer = new SentenceDecomposition().decompose("neotowheret", new String[]{"one", "two", "three", "there"});
		System.out.println("Time: " + (System.currentTimeMillis()-time)/1000.0 + " seconds");
		desiredAnswer = 8;
		System.out.println("Your answer:");
		System.out.println("\t" + answer);
		System.out.println("Desired answer:");
		System.out.println("\t" + desiredAnswer);
		if (answer != desiredAnswer)
		{
			errors = true;
			System.out.println("DOESN'T MATCH!!!!");
		}
		else
			System.out.println("Match :-)");
		System.out.println();
		time = System.currentTimeMillis();
		answer = new SentenceDecomposition().decompose("abba", new String[]{"ab", "ac", "ad"});
		System.out.println("Time: " + (System.currentTimeMillis()-time)/1000.0 + " seconds");
		desiredAnswer = 2;
		System.out.println("Your answer:");
		System.out.println("\t" + answer);
		System.out.println("Desired answer:");
		System.out.println("\t" + desiredAnswer);
		if (answer != desiredAnswer)
		{
			errors = true;
			System.out.println("DOESN'T MATCH!!!!");
		}
		else
			System.out.println("Match :-)");
		System.out.println();
		time = System.currentTimeMillis();
		answer = new SentenceDecomposition().decompose("thisismeaningless", new String[]{"this", "is", "meaningful"});
		System.out.println("Time: " + (System.currentTimeMillis()-time)/1000.0 + " seconds");
		desiredAnswer = -1;
		System.out.println("Your answer:");
		System.out.println("\t" + answer);
		System.out.println("Desired answer:");
		System.out.println("\t" + desiredAnswer);
		if (answer != desiredAnswer)
		{
			errors = true;
			System.out.println("DOESN'T MATCH!!!!");
		}
		else
			System.out.println("Match :-)");
		System.out.println();
		time = System.currentTimeMillis();
		answer = new SentenceDecomposition().decompose("ommwreehisymkiml", new String[]{"we", "were", "here", "my", "is", "mom", "here", "si", "milk", "where", "si"});
		System.out.println("Time: " + (System.currentTimeMillis()-time)/1000.0 + " seconds");
		desiredAnswer = 10;
		System.out.println("Your answer:");
		System.out.println("\t" + answer);
		System.out.println("Desired answer:");
		System.out.println("\t" + desiredAnswer);
		if (answer != desiredAnswer)
		{
			errors = true;
			System.out.println("DOESN'T MATCH!!!!");
		}
		else
			System.out.println("Match :-)");
		System.out.println();
		time = System.currentTimeMillis();
		answer = new SentenceDecomposition().decompose("ogodtsneeencs", new String[]{"go", "good", "do", "sentences", "tense", "scen"});
		System.out.println("Time: " + (System.currentTimeMillis()-time)/1000.0 + " seconds");
		desiredAnswer = 8;
		System.out.println("Your answer:");
		System.out.println("\t" + answer);
		System.out.println("Desired answer:");
		System.out.println("\t" + desiredAnswer);
		if (answer != desiredAnswer)
		{
			errors = true;
			System.out.println("DOESN'T MATCH!!!!");
		}
		else
			System.out.println("Match :-)");
		System.out.println();
		time = System.currentTimeMillis();
		answer = new SentenceDecomposition().decompose("sepawaterords", new String[]{"separate","words"});
		System.out.println("Time: " + (System.currentTimeMillis()-time)/1000.0 + " seconds");
		desiredAnswer = -1;
		System.out.println("Your answer:");
		System.out.println("\t" + answer);
		System.out.println("Desired answer:");
		System.out.println("\t" + desiredAnswer);
		if (answer != desiredAnswer)
		{
			errors = true;
			System.out.println("DOESN'T MATCH!!!!");
		}
		else
			System.out.println("Match :-)");
		System.out.println();
		
		
		if (errors)
			System.out.println("Some of the test cases had errors :-(");
		else
			System.out.println("You're a stud (at least on the test data)! :-D ");
	}

}
//Powered by [KawigiEdit] 2.0!
